﻿#include <iostream>

static int howManyMethodCountForMakePalindromicSubSequence(const char* str)
{
	if (!str) return 0;

	auto strLen = strlen(str);
	if (strLen <= 1) return strLen;

	int* dp = (int*)malloc(strLen * strLen * sizeof(int));
	memset(dp, 0, strLen * strLen * sizeof(int));

	for (int i = 0; i < strLen; i++)
	{
		dp[i + i * strLen] = 1;
		if (i + 1 < strLen)
		{
			dp[i + 1 + i * strLen] = str[i] == str[i + 1] ? 3 : 2;
		}
	}

	for (int i = strLen - 1 - 2; i >= 0; i--)
	{
		for (int j = i + 2; j < strLen; j++)
		{
			if (str[i] != str[j])
			{
				dp[j + i * strLen] = dp[j - 1 + i * strLen] + dp[j + (i + 1) * strLen] - dp[j - 1 + (i + 1) * strLen];
			}
			else
			{
				dp[j + i * strLen] = 1 + dp[j - 1 + i * strLen] + dp[j + (i + 1) * strLen];
			}
		}
	}

	int res = dp[strLen - 1];
	free(dp);
	return res;
}

/**
 * 对于一个字符串，从前开始读和从后开始读是一样的，我们就称这个字符串是回文串。例如"ABCBA","AA","A"是回文串，而"ABCD"，"AAB"不是回文串。牛牛特别喜欢回文串，他手中有一个字符串s，牛牛在思考能否从字符串中移除部分(0个或多个)字符使其变为回文串，并且牛牛认为空串不是回文串。牛牛发现移除的方案可能有很多种，希望你来帮他计算一下一共有多少种移除方案可以使s变为回文串。对于2种移除方案，如果移除的字符依次构成的序列不一样就是不同的方案。
 * 例如：XXY 4种；ABA 5种
 * 
 * 说明：
 * 这是今年的原题，提供的说明和例子都很让人费解。现在根据当时题目的所有测试用例，重新解释当时的题目含义：
 * 1) "1AB23CD21", 你可以选择删除A、B、C、D，选择什么样的删除顺序没有关系。
 * 2) "121A1", 其中有2个{1,2,1}的子序列，第一个{1,2,1}是由{位置0, 位置1, 位置2}构成，第二个{1,2,1}是由{位置0, 位置1, 位置4}构成。这两个子序列被认为是不同的子序列。也就是说在本题中，认为字面值一样但是位置不同的字符就是不同的。
 * 3) 其实这道题就是想求，str中有多少个不同的子序列，每一种子序列只对应一种删除方法，那就是把多余的东西去掉，而和去掉的顺序无关。
 * 4) 也许你觉得我的解释很荒谬，但真的是这样，不然解释不了为什么，XXY 4种，ABA 5种，而且其他的测试用例都印证了这一点。
 * 
 * 思路：
 * 动态规划范围尝试，i~j有多少种回文保留方案
 * 有4种可能性：
 * 1. 回文串以i开头，以j结尾
 * 2. 回文串不以i开头，不以j结尾
 * 3. 回文串不以i开头，以j结尾
 * 4. 回文串以i开头，不以j结尾
 * 
 * dp(i,j-1)涵盖了可能性2和4，因为它也包含了以i+1,i+2,...开头的情况。
 * dp(i+1,j)涵盖了可能性2和3，因为它也包含了以j-1,j-2,...结尾的情况。
 * dp(i+1,j-1)属于情况2
 * 
 * 重复的可能性需要减掉。
 * 如果str[i]≠str[j], 则可能性1不会发生，dp(i,j)=dp(i,j-1)+dp(i+1,j)-dp(i+1,j-1)
 * 如果str[i]==str[j], 则只保留str[i]和str[j]是一种可能性；去掉str[i]和str[j]，保留i+1~j-1这一段也是可能的，故这时dp(i,j)=1+dp(i+1,j-1)+(dp(i,j-1)+dp(i+1,j)-dp(i+1,j-1))
 * 
 * 
 * dp表一开始还是按照先填i==j的斜线格子，再填(0,1),(1,2),(2,3)...
 * 对于i==j, 由于只有1个字符，故只有保留这1个字符一种方法；
   对于(0,1),(1,2),(2,3)...如果str[i]==str[i+1], 则有3种方法，(1)保留str[i] (2)保留str[i+1] (3)保留str[i]和str[i+1]; 
   如果str[i]≠str[i+1], 则有2种方法，(1)保留str[i] (2)保留str[i+1], 其余的格子按照上文提到的是否以i开头，是否以j结尾的可能性分析.
 * 
 */
int main_removeSomeCharactersToMakePalindromicSequence()
{
	char str[] = "ABC";
	int howMany = howManyMethodCountForMakePalindromicSubSequence(str);
	printf("%d", howMany);
	return 0;
}